#include "sort.h"

void ShellInsert(SqList &L, int dk) {
    // 对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
    for (int i = dk+1; i < L.length; ++i)
        if (r[i].key < r[i-dk].key) {
            r[0] = r[i];
            for (j = i-dk; j > 0 && (r[0].key < r[j].key); j = j-dk)
                r[j + dk] = r[j];
            r[j+dk] = r[0];
        }
}


// dk值依次存放在dlta[t]中
void ShellSort(SqList &L, int dlta[], int t) {
    // 按增量序列dlta[0...t-1]对顺序表L作希尔排序
    for (int k = 0; k < t; ++k)
        ShellInsert(L, dlta[k]);    // 一趟增量为dlta[k]的插入排序
}